package LC;

/**
 * https://leetcode.com/problems/wildcard-matching/
 * Implement wildcard pattern matching with support for '?' and '*'.
 * '?' Matches any single character.
 * '*' Matches any sequence of characters (including the empty sequence).
 * The matching should cover the entire input string (not partial).
 * The function prototype should be:
 * bool isMatch(const char *s, const char *p)
 * Some examples:
 * isMatch("aa","a") → false
 * isMatch("aa","aa") → true
 * isMatch("aaa","aa") → false
 * isMatch("aa", "*") → true
 * isMatch("aa", "a*") → true
 * isMatch("ab", "?*") → true
 * isMatch("aab", "c*a*b") → false
 */
public class LC_044_WildcardMatching_TwoPointers {
    public static void main(String[] args) {
        String s = "aaa";
        String p = "*";
        boolean res = Solution.isMatch(s, p);
        System.out.println(res);
    }

    static class Solution {
        static boolean isMatch(String s, String p) {
            char[] chars = s.toCharArray();
            char[] charp = p.toCharArray();

            int ss = -1, pp = -1;
            int sIndex = 0, pIndex = 0;

            while (sIndex < chars.length) {
                if (pIndex == charp.length) {
                    if (pp == -1)
                        return false;
                    pIndex = pp + 1;
                    sIndex = ss++;
                } else if (charp[pIndex] == '?' || chars[sIndex] == charp[pIndex]) {
                    pIndex++;
                    sIndex++;
                } else if (charp[pIndex] == '*') {
                    pp = pIndex;
                    ss = sIndex;
                    pIndex = pp + 1;
                } else {
                    if (pp == -1)
                        return false;
                    pIndex = pp + 1;
                    sIndex = ss++;
                }
            }
            while (pIndex < charp.length) {
                if (charp[pIndex] != '*')
                    break;
                pIndex++;
            }
            return pIndex == charp.length;
        }
    }
}
